//
//  SGHStockPriceMaxViewController.m
//  DataStructuresAndAlgorithms
//
//  Created by blue on 2021/11/15.
//  Copyright © 2021 blue. All rights reserved.
//

#import "SGHStockPriceMaxViewController.h"

@interface SGHStockPriceMaxViewController ()

@end

@implementation SGHStockPriceMaxViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSArray *arr = @[@7,@1,@5,@3,@6,@4];
    CFAbsoluteTime   StartTime1 = CFAbsoluteTimeGetCurrent();
    function1(arr);
    CFAbsoluteTime EndTime1 = CFAbsoluteTimeGetCurrent();
    NSLog(@"function1执行时间为：----%f",EndTime1 - StartTime1);

    CFAbsoluteTime   StartTime2 = CFAbsoluteTimeGetCurrent();
    function2(arr);
    CFAbsoluteTime EndTime2 = CFAbsoluteTimeGetCurrent();

    NSLog(@"function2执行时间为：----%f",EndTime2 - StartTime2);
}

/**
 暴力破解法，二次for循环获取差值最大值
 **/
void function1(NSArray *arr) {
    int max = 0;
    int startIndex = 0;
    int saleIndex = 0;
 
    for (int i = 0 ; i < arr.count; i++) {
        for (int j = i+1; j<arr.count; j++) {
            //获取第j天股票价格
            int indexj = [arr[j] intValue];
            //获取第i天股票价格
            int indexi = [arr[i] intValue];
            int priceSpread  = indexj - indexi;
            if (priceSpread > max) {
                startIndex = i;
                saleIndex = j;
                max = priceSpread;
            }
        }
        
    }
    NSLog(@"第%d天买入，第%d天卖出，最大赚取max ----%d ",startIndex+1,saleIndex +1,max);
}

/**
动态规划
 1.获取最少购入价格
 2.判断最大售出价格
 **/
void function2(NSArray *arr) {
    int min = [arr[0] intValue];    //最小值
    int max = 0;   //最大赚取
    int startIndex = 0;
    int saleIndex = 0;
 
    for (int i = 1 ; i < arr.count; i++) {
        int indexi = [arr[i] intValue];
        //首先获取最少购入价格
        if (min > indexi) {
            min = indexi;
            //获取最大售出价格
        } else if (indexi - min > max) {
            /**
             切记这个开始位置，不是min的位置，
             如果数组NSArray *arr = @[@7,@2,@5,@13,@1,@5,@3,@6,@4,@8];
             是上面的话，min最终结果是1， startIndex应该是2的位置
             **/
            startIndex = [arr containsObject:@(min)];
            saleIndex = i;
            max = indexi - min;
        }
    }
    
    NSLog(@"第%d天买入，第%d天卖出，最大赚取max ----%d ",startIndex+1,saleIndex +1,max);
}

@end
